The present invention relates to implementations of the Viterbi algorithm, especially implementations that parallelize some of the steps of the Viterbi algorithm.
Viterbi decoding was developed by Andrew J. Viterbi. The seminal paper on the technique is “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm” published in IEEE Transactions on Information Theory, Vol. IT-13, pages 260-269, in April 1967. Viterbi decoding has been found to be optimal when the channel of the transmitted signal is corrupted by additive white Gaussian noise (AWGN). AWGN is noise whose voltage distribution over time has a characteristic that can be described using a Gaussian distribution (normal statistical distribution or bell curve distribution).
The Viterbi algorithm uses a trellis which restricts the number of state transitions. In the Viterbi algorithm, each new state has a specified number of possible state transitions from previous states. A branch metric comparing a selected value to an ideal value for a transition is calculated for each transition. The branch metric value is combined with a prior state path metric value, in order to produce updated candidate path metrics. For each new state, the candidate path metric with the lowest value is selected. An indication of the selected transition into the new state for that symbol is also stored.
FIG. 1 shows a conventional block diagram of a conventional Viterbi algorithm. In block 22, a branch metric calculation is done. The branch metric calculation compares the actual received value with the ideal received value for different symbol transmissions. In a binary symbol encoding system, for example, one of the transitions going into a state corresponds to the transmitted symbol “0”, and one of the transitions corresponds to the transmitted symbol “1.” The difference between the input symbol value and the value that would be received in the ideal case if a “1” is transmitted is the branch metric for the “1” transition and the difference between the received sample value and the ideal value if a “0” is transmitted would be the branch metric for the other branch. The branch metrics are added to the old value of the path metric for the source states. The two new candidate path metrics are compared to select the smallest (lower-energy) path metric. Unit 24 is typically called an add-compare-select (ACS) unit. The updated path metrics are stored in a path metric memory 26. In the system of FIG. 1, when the new path metric is produced, a traceback pointer is stored in the traceback pointer memory 28. The traceback pointer indicates the transition into the new state for one symbol. Trackback pointers are stored for every state of every symbol.
In the simplest state, the convolution encoder is reinitialized to an all-zero state at the end of a transmitted block of data. This typically means that at the receiver, state “0” is assumed to be the correct state after the transmission of the block. In the traceback algorithm, the data for each symbol transmitted needs to be examined to determine the transition of the decided path. This typically is a serial operation which takes at least as many steps as symbols within the transmitted block.
It is desired to have an improved method which speeds up the operation of the Viterbi algorithm.